#include "Graph.h"
#include <queue>

using namespace std;

void TopSort(Graph *g, int nodeIdx)
{
    int i, j;
    queue<GraphNode *> help;//辅助排序的队列
    help.push(g->nodeSet[nodeIdx]);
    //找到入度为0的节点作为起始节点
    for(auto n : g->nodeSet)
    {
        if(n->in == 0)
            help.push(n);
    }
    while(!help.empty())
    {
        auto cur = help.front();
        help.pop();
        printf("%d", cur->value);//可替换其它操作
        for(auto next: cur->nexts)
        {
            if(--next->in <= 0)//将新的入度为0的点入队
                help.push(next);
        }
    }
}

int dist[10005]; //因为计算最大值，所以初始化为0即可，若是寻最小，则需INT_MAX

//拓扑排序寻找最大路径（也可以寻找最小）
int TopFind(Graph* g)
{
    queue<GraphNode *> q;
    for(auto n : g->nodeSet)
    {
        if(n->in == 0)
        {
            q.push(n);
            dist[n->value] = n->weight;
        }
    }
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        //正常应该枚举边，当时做了一个特殊题目用了节点
        for(auto n : cur->nexts)
        {
            dist[n->value] = max(dist[n->value], dist[cur->value] + n->weight);
            if(--n->in == 0)
                q.push(n);
        }
    }
}